#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};


class Solution{
    private:
    vector<int> num;
    // int temp = 0;

    public:
    int ans1(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        front(root, temp);
        int sum = 0;
        for(int i = 0; i != num.size(); i++){
            sum += num[i];
        }
        num.clear();
        return sum;
    }

    void front(TreeNode* root, int value){
        if(root == nullptr){
            return;
        }
        value = root->val + value * 10;
        if(root->right == nullptr && root->left == nullptr){
            num.push_back(value);
        }
        front(root->left, value);
        front(root->right, value);
        value = value / 10;
    }


    void frontTraverse(TreeNode* root, vector<int>& val){
        if(root == nullptr){
            return;
        }
        val.push_back(root->val);
        frontTraverse(root->left, val);
        frontTraverse(root->right, val);
    }

    TreeNode* createTree(vector<int>nums, int index, int len){
        if(nums[index] == '#'){
            return nullptr;
        }
        TreeNode* root = new TreeNode(nums[index]);

        if(index * 2 + 1 < len){
            root->left = createTree(nums, index * 2 + 1, len);
        }else{
            root->left = nullptr;
        }
        if(index * 2 + 2 < len){
            root->right = createTree(nums, index * 2 + 2, len);
        }else{
            root->right = nullptr;
        }

        return root;
    }

    void show(vector<int>& val){
        int len = val.size();
        for(int i = 0; i != len-1; i++){
            cout << val[i] << " " << ends;
        }
        cout << val[len-1] << endl;
        val.clear();
    }


    // ans2
    int sumNumbers(TreeNode* root){
        frontOrder(root);
        return sum;
    }

    void frontOrder(TreeNode* root){
        if(root == nullptr){
            return;
        }

        temp = 10 * temp + root->val;
        if(root->left == nullptr && root->right == nullptr){
            sum = sum + temp;
        }
        frontOrder(root->left);
        frontOrder(root->right);
        temp = temp / 10;
    }

private:
    int sum = 0, temp = 0;

};

void test1(){
    Solution s;
    vector<int> nums = {1,2,3};
    TreeNode* root = s.createTree(nums, 0, nums.size());
    // int ret = s.ans1(root);
    int ret = s.sumNumbers(root);
    cout << ret << endl;
    
}

void test2(){
    Solution s;
    vector<int> nums = {4,9,0,5,1};
    TreeNode* root = s.createTree(nums, 0, nums.size());
    int ret = s.ans1(root);
    cout << ret << endl;

}

int main(void){
    test1();
    test2();

    return 0;
}